package com.uyong.study.algorithm.sort;

/**
 * 冒泡排序O(n^2),原地O(1),稳定
 * 
 * @author gonggy
 * @since 2019-01-29
 */
public class BubbleSort implements ISort {

	@Override
	public void sort(int[] data) {
		if (data.length <= 1) {
			return;
		}
		for (int i = 0; i < data.length; i++) {
			boolean swap = false; // 标记是否进行了数据交换，用于提前退出循环
			for (int j = 0; j < data.length - i - 1; j++) {
				if (data[j] > data[j + 1]) {
					int tmp = data[j];
					data[j] = data[j + 1];
					data[j + 1] = tmp;
					swap = true;
				}
			}
			if (!swap) {
				break; // 没有数据交换，说明已排好序，提前退出
			}
		}
	}
}
